mergeSort:: (Ord a) => [a] -> [a]
mergeSort [] = []
mergeSort [x] = [x]
mergeSort xs = merge ys zs 
			   where
					ys = mergeSort (take half xs)
					zs = mergeSort (drop half xs)	
					half = div size 2 
					size = length xs

merge:: (Ord a) => [a] -> [a] -> [a]
merge [] [] = []
merge xs [] = xs
merge [] ys = ys
merge (x:xs) (y:ys) | x < y = [x] ++ merge xs (y:ys)
					| y < x = [y] ++ merge (x:xs) ys
					| otherwise = [x,y] ++ merge xs ys

--como precondicion todos los elementos de la lista deben ser distintos

sub :: [Int] -> [Int]
sub xs = solucion ws []
	where 
		solucion [] ys = ys
		solucion (x:xs) ys  
			| x > 0 && ys == [] = [x]
			| x <= 0 = solucion xs (ys++[x])
			| otherwise = ys
		ys = mergeSort xs
		ws = dropWhile (/= (head ys)) xs

minima :: [Int] -> [Int] -> [Int]
minima [] ys = ys
minima (x:xs) ys 
	| x > 0 && ys == [] = [x]
	| x > 0 && ys /= [] = ys
	| otherwise = minima xs (ys++[x]) 


-- suma minima Divide and Conquer

-- prefijo de suma minima, precondicion: la lista tiene que tener como minimo un elemento
prefijo' :: [Int] -> Int -> Int -> Int
prefijo' [] minimo suma = minimo 
prefijo' (x:xs) minimo suma  
	| (suma + x) < minimo = prefijo' xs (suma+x) (suma+x)
	| otherwise = prefijo' xs minimo (suma+x)

-- precondicion: la lista tiene que tener como minimo un elemento
prefijo :: [Int] -> Int
prefijo (x:xs) = prefijo' xs x x 

minimo :: Int -> Int -> Int
minimo x y 
	| x < y = x
	| otherwise = y
	

subMinima :: [Int] -> Int
subMinima xs = minimo (minimo r e) t 
	where 
		r = min (prefijo primerMitad) (sufijo1)
		s = prefijo segundaMitad
		e = min s sufijo2
		sufijo1 = prefijo (ws)
		sufijo2 = prefijo (zs)
		zs = reverse segundaMitad
		ws = reverse primerMitad
		t = sufijo1 + s
		primerMitad = take half xs
		segundaMitad = drop half xs
		half = div size 2
		size = length(xs)
		
		
